This disclosure relates generally to error checking in digital systems and, more specifically, to a method and system for efficiently computing cyclic redundancy checks on data in a digital system.
Error checking is commonly used in digital communications, file back-up systems, and storage systems to verify that a message or file is free from errors (e.g., that the message or file being checked corresponds to the original message or file). One method for detecting such errors is to employ a cyclic redundancy check (CRC). The CRC performs a mathematical calculation on a block of data (e.g., the message or file) and returns a number (a “checksum”) that represents the content and organization of that data. The basic idea is to have the CRC return a checksum that uniquely identifies the data.
CRCs are widely used for a number of reasons. For example, a CRC is a fixed-length checksum (typically sixteen or thirty-two bits), data for which a CRC can be calculated can be of arbitrary length, there is a dependency on data order for computing a CRC, CRC is linear, and a CRC computation is of reasonable computational complexity.
In a digital communications system, a CRC may be used as follows. A data stream in a digital communications system consists of headers and data packets. As the data arrives at a source node, a CRC checksum is computed for the data and transmitted along with the data. A target node, upon reception of the data, independently generates the CRC checksum and compares the generated CRC checksum with the CRC checksum received from the source node. An exact match between the independently generated CRC checksum and the received CRC checksum indicates that there were no errors in the transmission. If the checksums do not match, an error is assumed to have occurred.
In file processing, CRC may be used as follows. An entire data file is considered as a data block for which a CRC checksum is calculated. The CRC checksum is stored along with the data. When the file data is restored, the CRC checksum is independently computed and checked against the pre-stored CRC checksum to check for errors. As in the case of communication systems, a CRC checksum match indicates that there were no errors in storage, whereas a mismatch indicates that an error occurred.
Generally, the CRC computation on a data block is accomplished in a serial manner and the entire data block has to be available. By using the linearity property of CRC, the computation may be made more efficient by pre-computing CRC tables, whose entries contain pre-computed effects on the CRC for any n-bit data, where n is usually 4, 6, or 8 bits. However, look-up tables become less desirable with increasing table index ‘n’, because they grow exponentially as 2n entries. Furthermore, there are situations where the entire data block for which the CRC is to be computed is not simultaneously available and the CRC checksum needs to be calculated on segments of the data block. This is generally accomplished by either employing data buffering to do the CRC computations, which results in processing delays, or computing the CRC checksum using alternative methods, such as computing a checksum for each data segment and then combining the data segments' checksums to obtain a final checksum.
Data buffering is often undesirable because it may affect performance (e.g., it requires additional read/write time to and from memory) and generally adds complexity to the CRC computations. Data buffering also requires that all the data for which the CRC needs to be computed is available before the computation starts, which slows down the receiving process that is waiting for the data. Some current methods for computing CRC checksums for multiple data segments and then combining them require constantly updating the CRC checksum while processing the CRC for each data segment, which adds computational complexity to the CRC computations. Other methods that compute CRC checksums for multiple data segments often use multiplication and polynomial division to obtain the final CRC checksum, which requires additional time and computational resources.
Therefore, what is needed is a method and system for efficiently computing CRCs on data in a digital system. For example, it is desirable to compute a CRC checksum for multiple segments and then to efficiently obtain a final CRC checksum.